//输入一个字符串，打印出该字符串中字符的所有排列。 
//
// 
//
// 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 
//
// 
//
// 示例: 
//
// 输入：s = "abc"
//输出：["abc","acb","bac","bca","cab","cba"]
// 
//
// 
//
// 限制： 
//
// 1 <= s 的长度 <= 8 
// Related Topics 回溯算法 
// 👍 148 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

//Java：字符串的排列
public class ZiFuChuanDePaiLieLcof{
    public static void main(String[] args) {
        Solution solution = new ZiFuChuanDePaiLieLcof().new Solution();
        
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    List<String> answer = new LinkedList<>();
    char[] chars ;
    public String[] permutation(String s) {
        chars = s.toCharArray();
        dfs( 0 );
        return answer.toArray(new String[answer.size()]);

    }
    //一层层的递归下去，而chars数组的头几个节点就是递归的层数，进行只需要交换其中的元素，就不至于重复
    //layer:层数 第一层是0层，类似数组下标的命名规则
    private void dfs(int layer) {
        if ( layer == chars.length - 1 ){
            answer.add( String.valueOf(chars) );
            return;
        }
        //记录已经查询过的字符，进行剪枝的操作
        HashSet<Character> hasTraversal = new HashSet<>();
        for (int i = layer; i < chars.length; i++) {
            //剪枝
            if ( hasTraversal.contains( chars[i] ) ){
                continue;
            }
            //就像是多个树一样，每棵树的根节点通过使用循环来确定，根节点不能重复
            //以及确定每个树的子节点，同一棵树的子节点不能重复
            hasTraversal.add( chars[i] );
            //先进行交换
            swap( i,layer );
            //接着深度遍历下去
            dfs( layer+1 );
            //进行恢复原样
            swap( i,layer );

        }
    }

    private void swap(int a, int b) {
        char temp = chars[a];
        chars[a] = chars[b];
        chars[b] = temp;
    }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
